package from_0_to_50;

import java.util.*;

public class Q047permuteUnique {
    static int[] stack;
    static boolean[] visit; // 相当于数的剪枝操作
    static boolean[] unique; // 相当于数的剪枝操作
    static List<List<Integer>> lists;
    static int top;
    public static void main(String[] args) {
        int[] a = new int[]{1,1,2};
        permuteUnique(a).forEach(list -> System.out.println(list));
        System.out.println("Math.pow(2,3) = " + (int)Math.pow(2, 3));


    }
    public static List<List<Integer>> permuteUnique(int[] nums) {
        lists = new ArrayList<>();
        stack = new int[nums.length];
        visit = new boolean[nums.length];  // 判断是否使用
        unique = new boolean[nums.length]; // 判断是否重复
        top = 0;
        dfs(top,nums);
        return lists;
    }
    public static void dfs(int top, int[] nums){
        if(top == nums.length){
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < top; i++){
                list.add(stack[i]);
            }
            lists.add(list);
        }
        System.out.println("Arrays.toString(visit) = " + Arrays.toString(visit));
        System.out.println("Arrays.toString(unique) = " + Arrays.toString(unique));
        System.out.println();
        if(top < nums.length){
            // 剪切 visit[i] == true + unique[i] == true 的值，余下即为递归的部分
            for(int i = 0; i < nums.length; i++){
                if(visit[i] == false && unique[i] == false){ // 0: noMark
                    visit[i] = true;
                    duplicateRemoval(nums);
                    stack[top++] = nums[i];
                    dfs(top,nums);
                    visit[i] = false;
                    duplicateRemoval(nums);
                    top--;
                }
            }
        }
    }
    public static void duplicateRemoval(int[] nums){
        for (int i = 0; i < unique.length; i++) {
            unique[i] = visit[i];
        }
        for (int i = 0; i < unique.length; i++) {
            if(unique[i] == true){
                continue;
            }
            for (int j = i+1; j < unique.length; j++) {
                if(nums[i] == nums[j])
                    unique[j] = true;
            }
        }
    }

}
